from typing import List


class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        dp = [[False for _ in range(k)] for _ in range(n)]
        dp[0][nums[0] % k] = True
        for i in range(1, n):
            for j in range(k):
                dp[i][j] |= dp[i-1][(j-nums[i])%k]
            if dp[i][0]: return True
        return False

if __name__ == '__main__':
    s = Solution()
    r = s.checkSubarraySum(nums = [23,2,4,6,7], k = 13)
    print(r)